package com.jia.leetCode;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @program: Leetcode
 * @description:
 * @author: STU756
 * @create: 2020-08-21 13:33
 */
public class Pro0354 {
    public int maxEnvelopes(int[][] envelopes) {
        int n = envelopes.length;
        //按宽升序排列，如果宽度医院，则按照高度降序排序
        Arrays.sort(envelopes, new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int[] b) {
                return a[0] == b[0]? b[1]-a[1] : a[0]-b[0];
            }
        });

        //对高度数组寻找LIS
        int[] heights = new int[n];
        for(int i = 0; i < n; i++) {
            heights[i] = envelopes[i][1];
        }
        return lengthOfLIS(heights);
    }
    //https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-she-ji-fang-fa-zhi-pai-you-xi-jia/
    public int lengthOfLIS(int[] nums) {
        int piles = 0;
        int n = nums.length;
        int[] top = new int[n];
        for(int i = 0; i < n; i++) {
            int poker = nums[i];
            int left = 0, right = piles;
            while(left < right) {
                int mid = (left + right) >> 1;
                if(top[mid] >= poker) {
                    right = mid;
                }else {
                    left = mid + 1;
                }
            }
            if(left == piles) piles ++;
            //吧这张牌放到牌的堆顶
            top[left] = poker;
        }
        //牌对数就是LIS长度
        return piles;
    }
}
